//
//
//class Solution {
//
//    List<List<String>> ret = new ArrayList<>();
//    List<String> path = new ArrayList<>();
//    char[][] arr;
//
//    public List<List<String>> solveNQueens(int n) {
//        arr = new char[n][n];
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                arr[i][j] = '.';
//            }
//        }
//        solveNQueens(n, 0);
//        return ret;
//    }
//
//
//    public void solveNQueens(int n, int index) {
//        if (index >= n) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for (int i = 0; i < n; i++) {
//            if (judge(index, i, n)) {
//                arr[index][i] = 'Q';
//                String str = new String(arr[index]);
//                path.add(str);
//                solveNQueens(n, index + 1);
//                path.remove(path.size() - 1);
//                arr[index][i] = '.';
//            }
//        }
//    }
//
//    public boolean judge(int x, int y, int n) {
//        for (int i = 0; i < n; i++) {
//            if (arr[x][i] == 'Q' || arr[i][y] == 'Q') return false;
//            for (int j = 0; j < n; j++) {
//                // (2,0)   n = 4
//                // 对角线 (3,1) (4,2) (5, 3)  i - x == j - y
//                // 反对角线 (1,1) (0,2) i+j == x+y
//                if (i - x == j - y && arr[i][j] == 'Q') return false;
//                if (i + j == x + y && arr[i][j] == 'Q') return false;
//            }
//        }
//        return true;
//    }
//}